public class CountSort {
    public static void countSort(int[]array){
        //遍历数组求最大值与最小值，以此获得极差创建计数数组
        //默认最大值与最小值均为起始元素
        int max=array[0];
        int min=array[0];
        //遍历数组获取最大值与最小值
        for(int i=1;i<array.length;i++){
            if(array[i]>max){
                max=array[i];
            }
            if(array[i]<min){
                min=array[i];
            }
        }
        //根据极差大小创建计数数组
        int[]count=new int[max-min+1];
        //遍历数组，根据映射关系开始计数
        for(int i=0;i< array.length;i++){
            //根据映射关系算出该元素在计数数组中的下标
            int index=array[i]-min;
            //对应位置计数加1
            count[index]++;
        }
        //计数完毕，开始遍历计数数组，输出到原数组中
        //设定原数组下标
        int index=0;
        for(int i=0;i< count.length;i++){
            //值相同的元素可能有多个，即计数数组中可能存在计数不为1的元素，需要多次取出
            while(count[i]>0){
                //根据映射关系取出元素
                int elem=i+min;
                //输出至原数组中
                array[index]=elem;
                //原数组下标移动
                index++;
                //计数数组对应计数减1
                count[i]--;
            }
        }
    }
}